class Solution
{
public:
    long long countPaths(int n, vector<vector<int>> &edges)
    {
        vector<vector<int>> graph(n + 1);
        for (auto &edge : edges)
        {
            graph[edge[0]].push_back(edge[1]);
            graph[edge[1]].push_back(edge[0]);
        }

        vector<int> isPrime(n + 1, 1);
        isPrime[0] = isPrime[1] = 0;
        for (long long num = 2; num <= n; ++num)
        {
            if (isPrime[num])
            {
                for (long long i = num * num; i <= n; i += num)
                {
                    isPrime[i] = 0;
                }
            }
        }

        // 从每个质数节点出发, 计算和它联通的合数子树的节点数
        long long ans = 0;
        for (int root = 2; root <= n; ++root)
        {
            if (!isPrime[root])
            {
                continue;
            }
            unordered_map<int, int> subTreeSizeCount;
            for (int subRoot : graph[root])
            {
                if (isPrime[subRoot])
                {
                    continue;
                }
                // bfs, 获得全部为合数的子树的节点数
                int subTreeSize = 0;
                queue<int> q;
                q.push(subRoot);
                unordered_set<int> visited;
                visited.insert(subRoot);
                while (!q.empty())
                {
                    int node = q.front();
                    q.pop();
                    ++subTreeSize;
                    for (int child : graph[node])
                    {
                        if (visited.count(child))
                        {
                            continue;
                        }

                        if (isPrime[child])
                        {
                            continue;
                        }

                        visited.insert(child);
                        q.push(child);
                    }
                }
                ++subTreeSizeCount[subTreeSize];
            }

            // 统计对答案的贡献
            for (auto p = subTreeSizeCount.begin(); p != subTreeSizeCount.end(); ++p)
            {
                long long s1 = p->first;
                long long c1 = p->second;
                ans += c1 * s1;
                for (auto q = p; q != subTreeSizeCount.end(); ++q)
                {
                    long long s2 = q->first;
                    long long c2 = q->second;
                    if (s1 == s2)
                    {
                        ans += c1 * (c1 - 1) / 2 * s1 * s1;
                    }
                    else
                    {
                        ans += c1 * c2 * s1 * s2;
                    }
                }
            }
        }

        return ans;
    }
};